/** 可放入背包的物品 */
type Articles = {
    weight: number, // 物品的重量
    value: number, // 物品的价值
    quantity: number, // 物品的拥有数量
};
/**
 * 背包问题：有一个容量为W的背包，还有一些带有各自重量和价值的物品，这些物品可重
 * 复并且有数量限制；求出将物品装入背包的最佳方案，使得总重量不超过W且总价值最大。
 * @param capacity 背包容量
 * @param articles 各自带有重量、价值和数量的物品
 */
export function knapSack(capacity: number, articles: Articles[]): number[] {
    // 容量为0或物品清单为空，无需计算直接返回
    if (!capacity || !articles.length) {
        return [];
    }
    // 将每个子问题的结果记忆化
    const cache: number[][] = [];
    /**
     * 内部方法，计算怎样装物品使得总价值最大，
     * 要保证物品数量不能超限、总重量不超过背包容量
     * @param curCapacity 当前容量
     */
    const getMaxValue = (curCapacity: number) => {
        // 当前容量不够
        if (curCapacity <= 0) {
            return [];
        }
        // 当前容量对应的最大价值已经算过了，直接取并返回
        if (cache[curCapacity] != null) {
            return cache[curCapacity];
        }

        // 当前容量（当前子问题）对应的解，也就是当前容量下怎样放物品价值最大
        let max: number[] = [];
        // 当前容量依赖的容量对应的解，也就是依赖容量下怎样放物品价值最大
        let newMax: number[];
        /*
            在当前容量curCapacity下，把每个物品作为当前视角，去计算该物品的价值加上剩余
            容量下的最大价值，最后得到这几个视角里最大的那一项；也就是在当前容量下各种
            组合的价值中取一个最大的。
        */
        for (let i = 0; i < articles.length; i++) {
            // 当前物品的重量
            const weight = articles[i].weight;
            // 当前容量所依赖的容量（剩余容量）
            const relyWeight = curCapacity - weight;
            // 依赖容量（剩余容量）要大于等于0，不然当前物品放不进来
            if (relyWeight >= 0) {
                // 依赖容量（剩余容量）最大价值的解
                newMax = getMaxValue(relyWeight);
                // 当前物品在依赖容量（剩余容量）里出现了几次
                const num = getNum(i, newMax);
                // 连接当前物品和依赖容量（剩余容量）里的解，也就是当前视角下的总价值
                const curMax = [i].concat(newMax);
                if (
                    (!max.length || isNewMax(curMax, max)) // 比之前视角下的价值还要大
                    && (num + 1 <= articles[i].quantity) // 并且数量没有超限
                ) {
                    // 只留下当前容量下各种组合中最大的那个
                    max = curMax;
                }
            }
        }
        // 记忆化当前容量下的最大价值
        cache[curCapacity] = max;
        return max;
    };
    // 谁的总价值最大
    const isNewMax = (a: number[], b: number[]): boolean => {
        let totalNewValue = 0;
        a.forEach(value => {
            totalNewValue += articles[value].value;
        });
        let totalValue = 0;
        b.forEach(value => {
            totalValue += articles[value].value;
        });
        return totalNewValue > totalValue;
    };
    // goal在array中出现过几次
    const getNum = (goal: number, array: number[]) => {
        if (array.length === 0) {
            return 0;
        }
        let num = 0;
        array.forEach(value => {
            if (goal === value) {
                num++;
            }
        });
        return num;
    };
    return getMaxValue(capacity);
}
/**
 * 0-1背包问题：有一个容量为W的背包，还有一些带有各自重量和价值的物品，这些物品不可重
 * 复放入；求出将物品装入背包的最佳方案，使得总重量不超过W且总价值最大。
 * @param capacity 背包容量
 * @param articles 各自带有重量、价值和数量的物品
 */
export function knapSack01(capacity: number, articles: Articles[]) {
    // 记忆化，二维数组，维度分别是物品和容量
    const kS: number[][] = [];
    const path: number[][] = [];
    // 初始化这个记忆化二维数组
    for (let i = 0; i <= articles.length; i++) {
        kS[i] = [];
        path[i] = [];
    }
    // 以每个物品为视角，计算在每一个容量下它的最大价值
    for (let i = 0; i <= articles.length; i++) {
        // 容量从0开始一直到capacity
        for (let w = 0; w <= capacity; w++) {
            // 0行0列要置为0，意思是没有物品或者容量为0其最大价值就是0
            if (i === 0 || w === 0) {
                kS[i][w] = 0;
            }
            // 当前物品放不进来，其价值就是前i-1个物品的价值
            else if (articles[i - 1].weight > w) {
                kS[i][w] = kS[i - 1][w];
            }
            // 当前物品能放进来，但可能有多余的容量（w - articles[i - 1].weight）
            else {
                const a = articles[i - 1].value + kS[i - 1][w - articles[i - 1].weight];
                const b = kS[i - 1][w];
                // 当前物品放进来，多余容量还能放其他物品，其价值还比前i-1价值大，那么当前最大价值就是a
                if (b < a) {
                    kS[i][w] = a;
                    // 存储这个解，当前最优解
                    path[i][w] = 1;
                } else { // 否则还是取前i-1的价值
                    kS[i][w] = b;
                }
            }
        }
    }
    // 最大价值对应的物品有哪些
    const result: number[] = [];
    for (let i = articles.length, j = capacity; i > 0 && j > 0; i --) {
        // 最优解
        if (path[i][j] === 1) {
            result.push(i - 1);
            // j--也可以
            j -= articles[i - 1].weight;
        }
    }
    return result;
}
